package org.example.recursion;

/**
 * @author carol
 */
public class BinarySearch {
    //递归二分查找

    public static int search(int[] a,int target){
        return f(a, target, 0, a.length - 1);

    }

    public static int f(int[] a,int target,int i,int j){
        if(j<i){
            return -1;
        }
        int m = (i+j)>>>1;

        if(target<a[m]){
            //向左查找 缩小范围
            return f(a,target,i,m-1);
        }else if(a[m]<target){
            //向右查找 缩小范围
            return f(a,target,m+1,j);
        }else {
            return m;
        }
    }

    public static void main(String[] args) {
        int[] a = {1,2,3,4,5,6,7,8,9};
        System.out.println(search(a, 5));
    }
}
